// https://www.lintcode.com/problem/permutations/my-submissions

class Solution {
public:
    /*
     * @param nums: A list of integers.
     * @return: A list of permutations.
     */
    
    // 法一：交换，交换开头数字，排列后面的
    // 和组合区别：在原数组上操作；start + 1 而不是 i + 1
    // void helper (vector<vector<int>> &results, vector<int> nums, int start, int end)
    // {
    //     if (start == end)
    //         results.push_back(nums);
    //     for (int i = start; i <= end; ++i)
    //     {
    //         swap(nums[start], nums[i]);
    //         helper(results, nums, start + 1, end);
    //         swap(nums[start], nums[i]);
    //     }
    // }
    // vector<vector<int>> permute(vector<int> &nums) {
    //     vector<vector<int>> result;
    //     if (nums.empty()) 
    //     {
    //         result.push_back(vector<int>());
    //         return result;
    //     }
    //     helper (result, nums, 0, nums.size() - 1);
    //     return result;
    // }
    
    // 法二：添加，向已有排列中添加元素，visited数组记录是否访问过
    void helper(vector<int> &nums, vector<vector<int>>& result, vector<int> &visited, vector<int>& permutation)
    {
        if (permutation.size() == nums.size())
        {
            result.push_back(permutation); //这个方法就不用判断为空了
        }
        for (int i = 0; i < nums.size(); ++i)
        {
            if (visited[i]) continue;
            visited[i] = true;
            permutation.push_back(nums[i]);
            helper(nums, result, visited, permutation);
            permutation.pop_back();
            visited[i] = false; //注意释放
        }
    }
    vector<vector<int>> permute(vector<int> &nums) 
    {
        vector<int> visited(nums.size(), false);
        vector<vector<int>> result;
        vector<int> permutation;
        helper(nums, result, visited, permutation);
        return result;
    }
};